#include <vector>
using namespace std;
void backtrace(vector<int> &nums, int i, int &minPath, const int step) {
  if (i >= nums.size() - 1) {
    minPath = min(minPath, step);
    return;
  }
  // 遍历当前跳的距离
  for (int j = 1; j <= nums[i]; ++j) {
    backtrace(nums, i + j, minPath, step + 1);
  }
}
int jump(vector<int> &nums) {
  int minPath = nums.size();
  int step = 0;
  backtrace(nums, 0, minPath, step);
  return minPath;
}

// 使用广度优先搜索优化跳跃时间
int jump_(vector<int> &nums) {
  int minPath = 0;
  int far = 0;
  int left = 0;
  int right = 0;
  while (right < nums.size() - 1) {
    for (int i = left; i <= right; ++i) {
      // 计算当前层能够跳到的最远距离
      far = max(far, i + nums[i]);
    }
    left = right + 1;
    right = far;
    minPath++;
  }
  return minPath;
}